Fast Fourier Transforms (FFTs) and Inverse Fast Fourier Transforms (IFFTs) are widely used in many signal processing applications. An FFT traditionally operates on data points and obtains Fourier coefficients. An IFFT traditionally operates on Fourier coefficients and recovers the data points. Modern applications, e.g., mobile devices, require an implementation that is efficient, flexible and low cost.
Existing solutions fail to satisfy these needs. While software FFT and IFFT solutions for general-purpose sequential processors and digital signal processors are inexpensive and flexible, they are generally inefficient. When the number of data points to compute an FFT or IFFT is small or fixed, traditional hardware can implement an efficient FFT or IFFT. However, such an implementation is usually expensive and highly inflexible. When the number of data points to compute an FFT or IFFT is large or variable, hardware implementations have been unavailable.
Meanwhile, technology based on reconfigurable pipelined and parallel computing architecture which promises to support high performance computing is emerging. Such architecture typically uses reconfigurable arrays of processing elements. Mapping an FFT or IFFT to this emerging architecture is a nontrivial exercise, especially for implementations that manage a large or variable number of data points.